
#pragma once

#include <ttg/services.h>
#include "CommonDefs.h"

using namespace ttg::services;

Point divide(const Points &P, Points &P_reduced, const Point &p1, const Point &p2) {
	Point farPoint = p1;
	double howFar = 0;
	for (Points::const_iterator it = P.begin(); it != P.end(); it++) {
		Point p = *it;
        if ( (p != p1) && (p != p2) ) {
			double cp = cross_product(p1, p2, p);
            if (cp > 0) {
                P_reduced.push_back(p);
                if (cp > howFar) {
                    farPoint = p;
                    howFar   = cp;
                }
            }
        } 
	}
    return farPoint;
} 

void divide_and_conquer(const Points &P, Points &H, Point p1, Point p2) {
    if (P.size() < 2) {
        H.push_back(p1);
        H.insert(H.end(), P.begin(), P.end());
    }
    else {
        Points P_reduced;
        Points H1, H2;
        Point p_far;

        p_far = divide(P, P_reduced, p1, p2);

        divide_and_conquer(P_reduced, H1, p1, p_far);
        divide_and_conquer(P_reduced, H2, p_far, p2);

        H.insert(H.end(), H1.begin(), H1.end());
        H.insert(H.end(), H2.begin(), H2.end());
    }
}

double serialConvexHull(const Points &points, Points &res)
{
    res.clear();

	double t_start = ServiceBase::_Timer().getSeconds();
    Point p_maxx = getMaxX(points);
    Point p_minx = getMinX(points);
    Points H;
    divide_and_conquer(points, res, p_maxx, p_minx);
    divide_and_conquer(points, H, p_minx, p_maxx);
	double t_end = ServiceBase::_Timer().getSeconds();
    res.insert(res.end(), H.begin(), H.end()); 
	return t_end - t_start;
}
